package leetcode.code0996;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	Set<Integer>[] nxt;
	int ans;
	int[] nums;

	public int numSquarefulPerms(int[] nums) {
		this.nums = nums;
		int len = nums.length;
		nxt = new HashSet[len];
		for (int i = 0; i < len; i++) {
			nxt[i] = new HashSet<>();
		}
		for (int i = 0; i < len; i++) {
			int n1 = nums[i];
			for (int j = i + 1; j < len; j++) {
				int sum = n1 + nums[j];
				int n = (int) Math.sqrt(sum);
				if (n * n == sum) {
					nxt[i].add(j);
					nxt[j].add(i);
				}
			}
		}
		ans = 0;
		int limit = (1 << len) - 1;
		Node root = new Node();
		for (int i = 0; i < len; i++) {
			f(limit ^ (1 << i), i, root);
		}
		return ans;
	}

	private void f(int rest, int end, Node root) {
		if (rest == 0) {
			if (!root.containsKey(nums[end])) {
				ans++;
				root.put(nums[end], new Node());
			}
			return;
		}
		if (root.containsKey(nums[end])) {
			return;
		}
		Node node = root.computeIfAbsent(nums[end], key -> new Node());
		Set<Integer> next = nxt[end];
		for (int n : next) {
			if ((rest & (1 << n)) != 0) {
				f(rest ^ (1 << n), n, node);
			}
		}
	}

	class Node extends HashMap<Integer, Node> {
		
	}

	@Override
	public void debug4() {
		H.compare(6, this.numSquarefulPerms(H.str2array3("[2,2,7,7,2]")));
//		H.compare(2, this.numSquarefulPerms(H.str2array3("[1,17,8]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
